package com.bupt.service.common.impl;

import com.bupt.basic.BasicNetWork;
import org.springframework.stereotype.Repository;

import java.util.*;

@Repository
public class TbAlgorithms {

    public static List<BasicNetWork.BasicLink> findNoMust(Set<BasicNetWork.BasicLink> links, Set<BasicNetWork.BasicNode> nodes,
                                                   BasicNetWork.BasicNode origin, BasicNetWork.BasicNode destination,
                                                    String strategy, BasicNetWork basicNetWork) {
        // 校验参数
        if (links == null || nodes == null || origin == null || destination == null) {
            return null;
        }
        // 校验 起点和终点在集合中
        if (!nodes.contains(origin) || !nodes.contains(destination)) {
            return null;
        }
        Map<BasicNetWork.BasicNode, Integer> nodeIntegerMap = new HashMap<>();//节点坐标字典
        Map<Integer, BasicNetWork.BasicNode> integerNodeMap = new HashMap<>();// 节点坐标反字典
        int size = nodes.size();//矩阵大小
        int[][] adjacentMatrix = new int[size][size];//图矩阵
        int ori = 0;//起点
        int des = 0;//终点
        //寻找起点和终点的引用，并确定节点的坐标字典
        int n = 0;
        for (BasicNetWork.BasicNode node : nodes) {
            if (node.equals(origin)) {
                ori = n;
            }
            if (node.equals(destination)) {
                des = n;
            }
            nodeIntegerMap.put(node, n);
            if (nodeIntegerMap.get(node) == null) {
                System.out.println(node.getName());
            }
            integerNodeMap.put(n, node);
            n++;
        }

        //初始化矩阵
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (i == j) {
                    adjacentMatrix[i][j] = 0;
                } else {
                    adjacentMatrix[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        //设置矩阵
        for (BasicNetWork.BasicLink link : links) {
            if (link == null) {
                continue;
            }
            BasicNetWork.BasicNode fromNode = basicNetWork.getNodeMap().get(link.getNodeHead());
            BasicNetWork.BasicNode toNode = basicNetWork.getNodeMap().get(link.getNodeTail());
            if (nodeIntegerMap.get(fromNode) == null || nodeIntegerMap.get(toNode) == null){
                continue;
            }
            int fromNumber = nodeIntegerMap.get(fromNode);
            int toNumber = nodeIntegerMap.get(toNode);
            adjacentMatrix[toNumber][fromNumber] = (int) weightOf(link,strategy);
            adjacentMatrix[fromNumber][toNumber] = (int) weightOf(link,strategy);
            //adjacentMatrix[nodeIntegerMap.get(link.getToNode())][nodeIntegerMap.get(link.getFromNode())] = (int) weightOf(link);
            //adjacentMatrix[nodeIntegerMap.get(link.getFromNode())][nodeIntegerMap.get(link.getToNode())] = (int) weightOf(link);
        }
        //算路
        List<Integer> route = routeCalculation(adjacentMatrix, ori, des);
        if (route == null) {
            return null;//没有路由
        }
        //生成路由
        List<BasicNetWork.BasicLink> returnLink = new ArrayList<BasicNetWork.BasicLink>();
        for (int i = 0; i < route.size() - 1; i++) {
            BasicNetWork.BasicNode from = integerNodeMap.get(route.get(i));
            BasicNetWork.BasicNode to = integerNodeMap.get(route.get(i + 1));
            for (BasicNetWork.BasicLink link : links) {
                if ((link.getNodeHead().equals(from.getNodeId()) && link.getNodeTail().equals(to.getNodeId())) ||
                        (link.getNodeHead().equals(to.getNodeId()) && link.getNodeTail().equals(from.getNodeId()))) {
                    returnLink.add(link);
                    break;
                }
            }
        }
        return returnLink;
    }

    public static List<BasicNetWork.BasicLink> findOneMust(Set<BasicNetWork.BasicLink> links, Set<BasicNetWork.BasicNode> nodes, BasicNetWork.BasicNode origin, BasicNetWork.BasicNode destination,
                                                    BasicNetWork.BasicNode mustNode, String strategy,BasicNetWork basicNetWork) {
        if (origin == null || destination == null || mustNode == null) {
            return null;
        }
        //生成路由1和2
        List<BasicNetWork.BasicLink> returnLink1 = findNoMust(links, nodes, origin, mustNode,strategy,basicNetWork);
        if (returnLink1 == null || returnLink1.isEmpty()) {
            return null;
        }
        List<BasicNetWork.BasicLink> returnLink2 = findNoMust(links, nodes, mustNode, destination,strategy,basicNetWork);
        if (returnLink2 == null || returnLink2.isEmpty()) {
            return null;
        }
        //两个路由链路组都找到了
        for (BasicNetWork.BasicLink basicLink : returnLink2) {
            if (!returnLink1.contains(basicLink)) {
                returnLink1.add(basicLink);
            }
        }
        return returnLink1;
    }

    //根据链路选定的策略，计算链路的权值，有可能返回最大值，有溢出风险
    private static double weightOf(BasicNetWork.BasicLink link,String strategy) {
        switch (strategy) {
            case "HOP":
                return 1.0;
            case "LENGTH":
                double length = 10.0;
                if(link.getLength()!=null) {
                    length = (double)link.getLength();
                }
                return length;
            default:
                double free = 1.0;
                if (link.getFreeRate() == null) {
                    if (link.getRate() != null) {
                        free = link.getRate();
                    }
                } else {
                    free = link.getFreeRate() * 0.1;
                }
                if (free <= 0) {
                    return Double.MAX_VALUE;//注意有溢出风险
                }
                double lengthDefault = 10.0;
                if(link.getLength()!=null) {
                    lengthDefault = (double)link.getLength();
                }
                return lengthDefault / free;
        }
    }

    public static List<Integer> routeCalculation(int[][] adjacentMatrix, int origin, int destination) {
        int size = adjacentMatrix[1].length;//获取邻接矩阵大小
        int[] distance= new int[size];//最短路长度
        boolean[] flag= new boolean[size];//标记i顶点最短路有无找到
        int[] prev=new int[size];//前驱数组
        ArrayList<Integer> route = new ArrayList<Integer>();//路由数组
        //初始化
        for(int i = 0 ; i < size ; i++) {
            distance[i] = adjacentMatrix[origin][i];//初始化距离都为起点到各个点的权值
            flag[i] = false;//起点到各个点的最短路径还没获取到
            if(distance[i] < Integer.MAX_VALUE  && distance[i] != 0) prev[i]=origin;
            else prev[i] = -1;//各个顶点的前驱点为-1
        }
        //对起点进行初始化
        flag[origin]=true;
        distance[origin]=0;//起点到起点的距离为0

        //遍历邻接矩阵size次；每次找出一个顶点的最短路径
        int now = origin;
        int before;
        for(int i =0;i<size;i++) {
            before = now;
            //寻找当前的最短路径
            //即在为获取最短路径的顶点中，找到离起点最近的顶点（k）
            int min=Integer.MAX_VALUE;
            for(int j=0;j<size;j++) {
                if(flag[j]==false && distance[j] < min) {
                    min=distance[j];
                    now=j;
                }
            }
            if(now == before )break;//没有新节点的情况
            //标记"节点now"为已经获取到最短路径
            flag[now] = true;
            //修正当前最短路径和前驱节点
            for(int j=0;j<size;j++) {
                if(flag[j]==true)continue;
                int tmp=(adjacentMatrix[now][j]==Integer.MAX_VALUE ? Integer.MAX_VALUE:(min+adjacentMatrix[now][j]));
                if(tmp < distance[j]) {
                    distance[j]=tmp;
                    prev[j]=now;
                }
            }
        }
        //获取路由数组
        Stack<Integer> stack= new Stack<Integer>();
        int topPtr=destination;
        if(prev[topPtr] == -1)return route;
        stack.push(topPtr);
        while(topPtr!=origin) {
            topPtr=prev[topPtr];
            stack.push(topPtr);
        }
        while(!stack.empty()) {
            route.add(stack.pop());
        }
        return route;
    }
}
